1. Field of the Invention
The present invention generally relates to computer implementable decision support systems for determining a production schedule of feasible material releases within a complex multi-stage manufacturing system architecture. In more particularity, the present invention relates to a system for rationing manufacturing resources among competing demands according to a defined set of business rules.
2. Background Description
The manufacturing of semiconductors is a complex and refined process. This process includes everything from growing silicon crystals, to the actual placement and soldering of chips to a printed circuit board. Initially, raw wafers are cut from a silicon ingot and processed through a specific sequence of work centers. The end goal of this process is to build a set of integrated circuits on the surface of the silicon wafer according to a specific circuit design. This process involves repeatedly applying four basic steps: deposition, photolithography, etching, and ion implantation. These steps are the means by which materials with specific dielectric properties (e.g., conductors, insulators) are deposited on the surface of the wafer according to the precise circuit design specifications. These steps are repeated many times to build up several layers (typically between 12 and 25 layers) of the circuits.
After the circuits have been built on the wafers they are tested to determine the resultant yield of operational circuits and tagged for later reference. The circuits are then diced and sorted, and subsequently wire bonded to a substrate to assemble a module. These modules, which are further tested to determine electromagnetic and thermal characteristics, are eventually combined on printed circuit boards to form cards. Finally, the cards are tested and those that pass are eventually used in the assembly of a wide range of finished electronic products (e.g., personal computers, printers, CD players, etc.). From the point of view of semiconductor manufacturing, the modules and cards are, mostly, the finished products taken to market.
To assemble the modules and cards (or other end products), a Bill of Material (BOM) is needed to specify the required components used in the assembly of each particular part number (PN) produced within the manufacturing system. The BOM can be used to generate a graphical representation of the stages within a manufacturing process for each of the finished products. For example, FIG. 1 shows a high level block diagram of the BOM for semiconductor manufacturing which can be broken into the following four aggregate stages: wafer stage 110, device/substrate stage 120, module stage 130, and card stage 140. These aggregate stages may involve many steps each of which may significantly impact the flow of materials through the manufacturing system. For example, the wafer stage 110 may involve wafer fabrication involving many passes through photolithography work centers to build multiple levels of a circuit structure. The dicing of the silicon wafer stage 120 involves a single item in the production process which is then converted into different devices. Also, the card stage 140 may involve the assembly of many devices to generate a single card. These stages result in multiple qualities of items being output from various stages of the manufacturing system according to a known distribution.
Resource requirements at various stages in the manufacturing system play an important role in the development of a feasible production schedule in most industries. These resources are typically machines for carrying out the above mentioned processes in semiconductor manufacturing and may include items such as furnaces, cutting tools for dicing chips, and testing machines for determining the operational characteristics of devices. Typically, insufficient resources are available to accommodate perfect just-in-time processing at the various manufacturing stages for all orders. Thus, the finite availability of resources must be accounted for in computing a schedule, and in some cases processing must be carried out earlier or later than desired depending on such availability. A property of resource requirements which is typical in semiconductor manufacturing, but not common to most industries, is the fact that a component processed within the manufacturing system may have to revisit the same resource many times. This is referred to as reentrant flow scheduling.
In addition to the BOM, other sources of manufacturing information such as yields, cycle times, shipping routes, etc. are critical for advance planning and scheduling of the product. However, a fundamental problem faced in all manufacturing industries is the matching of demand and assets over a set time period. By way of example, production lead times necessitate the advance planning of production so that material releases throughout the production system are coordinated with the end customers demand for any of a wide range of finished products (typically on the order of thousands in semiconductor manufacturing). Such advance planning depends on the availability of finite resources which include, for example, finished goods inventory, work in process (WIP) at various stages of the manufacturing system and work center capacity. Furthermore, there may be multiple locations, processes, and work centers that may be utilized for a particular job.
As is known, product advance planning decisions are necessary due to the complicated process architecture and unavoidably long lead times to complete processing through all manufacturing stages for a finished product. For this reason and to accommodate the planning and scheduling functions within the semiconductor manufacturing industry, a tiered planning system was devised. The following is a summary based on the tier system devised by Sullivan, G. and Fordyce, K., 1990, xe2x80x9cIBM Burlington""s Logistics Management Systemxe2x80x9d, Interfaces, 20, 1, 43-64. In this tiered system each tier is defined by the time frame to which the decisions pertains.
Tier 1: Long range (3 months to 7 yr) strategic level decisions such as mergers, capacity acquisition, major process changes, new product development, and long term policy based decisions.
Tier 2: Medium range (1 week to 6 months) tactical scheduling involving yield and cycle time estimation, forecasting and demand management, material release planning and maintenance scheduling.
Tier 3: Short to medium range (weekly planning) operational scheduling for optimizing consumption and allocation of resources and output of product, demand prioritization techniques, capacity reservation and inventory replenishment.
Tier 4: Short range (daily) dispatch scheduling for addressing issues such as machine setups, lot expiration, prioritizing of late lots, job sequencing, absorbing unplanned maintenance requirements and assigning personnel to machines.
The above taxonomy of planning and scheduling decisions is a hierarchical one, i.e., decisions in higher tiers affect lower tiers. For example, long range capacity acquisition decisions determine eventual yield and cycle times, the available resources that can be utilized, and the extent to which maintenance is to be scheduled in the future. As is known, decisions in higher tiers, by the nature of their long time frames, are made under considerable uncertainty and thus seek to anticipate future requirements based on current information. On the other hand, lower level tier decisions are of a corrective/reactive nature and act to absorb uncertainty not accounted for in the higher tiers. It is also noted that advanced production planning and scheduling decision support systems are typically run on a weekly basis; however, the planning horizon for such runs may range several years depending on the planning horizon of interest and the level of detail in forecasting. Thus, advance planning systems may impact decisions in tiers 1, 2 and 3 which, in turn, may affect tier 4 decisions. Therefore, the matching of assets to demand is a major planning activity which affects decisions within all tiers.
It is noted that if unlimited assets were available then the matching of demand with assets would be straightforward. In reality, however, finite supply and capacity create constraints on production scheduling. These constraints make the determination of a feasible production schedule (let alone an optimal one) a complex problem. The production schedule, which includes major activities involved in the production planning process, can be divided into three categories: Supply Aggregation (SA), Materials Requirements Panning (MRP) and Resource Allocation (RA).
Supply Aggregation (SA)
The Supply Aggregation involves capturing and transforming micro/factory floor details into a manageable data set. For example, WIP at a particular work center in the manufacturing system may ultimately travel through a variety of different routings. These routings depend on which type of finished product is eventually produced by the WIP. However, at any given point in the system a set of operations can be isolated which are common to all potential routings that the WIP can travel through from that point forward. In other words, a limited set of the immediate future operations required for the WIP are known.
The purpose of the Supply Aggregation step is then to project the WIP forward through the required work centers to points at which decisions regarding alternative routings are necessary. As the WIP is moved forward, its amount is adjusted for yield losses at the work centers through which it has traveled. Furthermore, the time at which the WIP becomes available at the projected work center is computed based on known cycle times at each work center. In reality, these times occur over a continuum; however, in practice, these times are discretized into a finite set of time periods. The end result of the Supply Aggregation is then to significantly reduce the number of material release points considered in future calculations which, in turn, decreases computation time to compute a feasible production schedule.
Material Requirements Planning (MRP)
Material Requirements Planning (MRP) is a well known production scheduling method based on xe2x80x9cexplosionxe2x80x9d of finished product demand using manufacturing information such as the BOM, yield and cycle times, inventory and planned receipts. The MRP is based on taking demand for finished product and sequentially moving backwards through the BOM (exploding). Required material releases are determined as well as the ideal release date based on cycle times at each work center at each level of the BOM.
Specialized process dependent factors in semiconductor manufacturing introduce additional complexities beyond those that can be readily handled by basic MRP. These additional complexities may result from material substitution or binning, both of which must be accounted for in computing production schedules. For example, at certain stages of the manufacturing process there is the opportunity for material substitution in which higher quality items are substituted for lower quality items (e.g., 900 MHz processor substituted in place of a 700 MHz processor). Another important process specific to semiconductor manufacturing is binning which refers to a distribution of quality levels for circuits built on a silicon wafer. The effect of binning is to link decisions about material releases among multiple PNs within the BOM which subsequently requires the use of large scale optimization methods, typically linear programming (LP) based models. The production scheduling system which incorporates LP in generating material releases to account for binning and material substitutions is referred to as Advanced Material Requirements Planning (AMRP). See, U.S. Pat. No. 5,943,484, which is incorporated herein by reference in the entirety.
Resource Allocation (RA)
MRP generates a set of ideal material releases under the assumption that unlimited resources are available. The purpose of Resource Allocation is then to systematically adjust this ideal set of releases to make them feasible with respect to constraints due to limited resources. That is, RA is concerned with the allocation of limited capacity to generate a feasible production schedule.
Historically a broader group of methodologies, referred to as extended MRP or MRP II, have included steps in which capacity requirements are evaluated based on releases generated by MRP. A method called xe2x80x9cBest Can Doxe2x80x9d (BCD) (see, U.S. Pat. No. 5,971,585), which uses linear programming, extends the capability of MRP II based systems from analysis to the actual development of a near optimal production schedule. This involves moving up from lower to higher levels of the BOM (implosion) and allocating resources sequentially at each level based on a priority ranking of the MRP material releases (which are, in turn, determined by priority ranking of orders they support). The resources allocated, using these systems, can be separated into two groups, supply and capacity. The fundamental difference between these two types of assets is that unapplied supply is available to apply at a later period; whereas, unapplied capacity is not available to apply at a later period. When supply and/or capacity constraints are violated by the MRP releases, the schedule of releases is adjusted in time by moving a portion of the release to an earlier period if possible and otherwise a sufficiently later period in time such that the required supply and capacity are available.
Plans generated using MRP are often referred to as ideal plans since they are uncapacitated (they assume unlimited supply and capacity). With this said, various rough-cut capacity planning methods have been documented in the literature ((xe2x80x9cFactory Physics: Foundations of Manufacturing Managementxe2x80x9d, Hopp, W. J., Spearman M. L., 1996, Irwin, Chicago). The nature of these methods is to determine when capacity constraints are violated rather than how to generate a feasible schedule. Detailed capacitated material release scheduling has been less explored.
Most modern production planning heuristics calculate low level codes (LLC). These are codes which are computed and assigned to each of the PNs in the BOM so that MRP and RA heuristics know which sequence to process the PNs. For instance, the PROFIT(trademark) BCD heuristic first conducts an xe2x80x9cexplosionxe2x80x9d (MRP) moving downwards through the BOM supply chains and then conducts an xe2x80x9cimplosionxe2x80x9d (RA) moving upwards through the BOM supply chains. During this implosion, the resulting production plan is forced to be feasible subject to constraints on available component supply and capacity resources by adjusting the MRP scheduled releases, in time, by moving them earlier, if possible, or later in time, if necessary. For both the explosion and implosion, production plans are determined level by level, according to the sequence defined by the assignment of LLCs, where the entire time horizon is planned for the complete set of components at a given LLC. Thus, the computation of LLCs is a critical preprocessing step to the complete production scheduling system.
The concept of allocating capacity sequentially according to an imposed ranking requires special attention within a complex multi-stage manufacturing system. In a typical model, dependency among PNs within the BOM is tracked by using LLCs. By way of example and again referring to the example of FIG. 1, wafers are used to produce devices/substrates which are then used to produce modules and, in turn, cards. In this example, the LLC assignment to the different levels would be: level 1 for cards, level 2 for modules, level 3 for devices/substrates and level 4 for wafers. In more complicated cases, in which there are many PNs and complicated interdependency, the assignment of LLCs is less trivial. The following algorithm, similar to others presented previously in the literature, can be used for systematically computing LLCs:
Step 1: Assign all PNs with demand to an initial LLC of 1. Set variable ITERATION=1.
Step 2: For all PNs in the BOM with LLC=ITERATION and that are components of another PN with LLC=ITERATION increase their LLC by one. Then, increment ITERATION by one.
Step 3: If no PN with LLC=ITERATION that is a component of another PN with LLC=ITERATION then stop. Otherwise return to step 2.
This algorithm takes as input a table containing all individual BOM dependencies between each given PN and its components. The basic idea of the algorithm is to begin by assigning all PNs to the same (highest) level. Using the BOM, PNs in the lowest level (i.e., with the highest LLC) are tested to determine whether they need to be promoted to the next level due to dependency within their current level. Finally, through iterations, PNs which are components of other PNs are moved to the next level of the BOM (a process referred to as bumping).
FIG. 2 is an example that illustrates the application of the algorithm described above. The individual PN-component BOM relationships are shown at level 210. This list of records for part numbers (indicating which components are required for assembly) is used to assign LLCs to each PN. Thus, initially in level 220, according to step 1 of the above algorithm, all PNs are assigned a LLC of xe2x80x9c1xe2x80x9d and ITERATION is set to xe2x80x9c1xe2x80x9d. At step 2 of the algorithm, a determination is made among PNs with LLC xe2x80x9c1xe2x80x9d which ones are components to other PNs with LLC xe2x80x9c1xe2x80x9d. The result in this case is that B, C and D are determined (from the list in level 210) to be components and, therefore, should have their LLCs increased by xe2x80x9c1xe2x80x9d. Increasing ITERATION by xe2x80x9c1xe2x80x9d to xe2x80x9c2xe2x80x9d and using connecting lines to identify BOM dependency yields the results of level 230. Next, in step 3 of the algorithm described above, it is determined that some PNs have LLC=ITERATION and therefore the algorithm returns to step 2. The algorithm proceeds to assign codes as is shown in level 240 until no further changes are necessary in level 250, i.e., no PN has LLC=ITERATION where ITERATION=5.
The above prior art algorithm for LLCs does not account for special requirements imposed by processes common in semiconductor manufacturing such as binning and material substitution. As mentioned above, binning occurs when a certain manufacturing stage generates a range of qualities. These different quality products correspond to different PNs, however, it is desirable for these PNs to have the same LLC so that they are considered together during the RA phase of production scheduling. Similarly, it is desirable for PNs, that can substitute for one another, to have the same LLC. To account for these special properties of the BOM, modifications are necessary. These modifications are described in U.S. Pat. No. 5,943,484, having a common assignee and incorporated herein by reference in its entirety. The basic modifications involve classifying PNs as siblings that either (a) result from the same binning process or (b) can be substituted for or by that part number. Thus, in the above prior art algorithm if a given PNs LLC is increased in step 2 then so are the LLCs of its siblings.
It is noted that the above algorithm is suitable only for MRP based algorithms that are applied to traditional manufacturing systems. However, the specialized processes in semiconductor manufacturing (e.g. binning, material substitution), and algorithmic requirements for using RA to compute capacitated production schedules that are consistent with accepted business rules, make such an algorithm inadequate for complex manufacturing processes such as those encountered in semiconductor manufacturing.
FIG. 3 further shows the problem with allocating capacity by traditional LLC generation. Assuming the following:
(i) PN A is made from PN B
(ii) PN B is made from PN C
(iii) PN C is made from PN D
(iv) PN X is made from PN Y
(v) PN Y is made from PN Z.
In this case, known LLC generators would compute LLC codes for components A, B, C, and D as 1, 2, 3, and 4, respectively, and components X, Y, and Z as 1, 2, and 3, respectively. Consequently, a heuristic such as MRP would first process components A and X (LLC=1), then components B and Y (LLC=2), then components C and Z (LLC=3), and finally component D (LLC=4). This is adequate until capacity is considered. consider the situation in which B and X share the same resource. In the RA implosion stage, the finite capacity of this resource is allocated by starting at the lowest LLC (LLC=4) and moving upwards. Thus, in this case B would receive priority in allocation of capacity over X since it would be processed first. Although, based on established business priorities, it may be desirable to instead give X priority over B thus illustrating the possible failure of traditional LLC generators.
As seen, allocating limited manufacturing resources to achieve a feasible production schedule that is consistent with customer demand is a difficult and common problem faced in many industries. For large-scale multi-stage manufacturing systems the problem is further complicated by the fact that many different parts produced within the manufacturing system share finite capacity resources. Traditional material requirements planning systems assign a numeric code, LLC, to represent the dependence of parts upstream in the bill of material supply chain with those downstream. However and as discussed above, these methods do not capture the need for resource sharing that is created when parts at different levels require the same resources.
According to an aspect of the invention, a method is provided for computing modified low level codes (LLC) for part numbers throughout a bill of material (BOM) supply chain. The method includes identifying part numbers that share a same capacity resource but cannot be made to have a same LLC due to a BOM material restriction. The part numbers which cannot be made to have the same LLC due to the BOM material restriction are oscillating part numbers (OPN). The highest LLC within the part numbers that share the same capacity resource except for the OPN is identified, and the LLC for the part numbers that share the same capacity resource, excluding the OPN, to the highest LLC are adjusted such that the part numbers which share the same capacity resource have a same LLC. The method then recalculates the LLC for part numbers which violate BOM dependencies by going through the entire BOM supply chain. The recalculated LLC is higher than or equal to the highest LLC provided in the adjusting step for each capacity resource. The adjusting of the LLC to the same LLC permits part numbers at different levels of the BOM which share the same capacity resource to be treated at a same level of the BOM in order to sequence the part numbers for resource allocation.
In accordance with another aspect of the present invention, the method of the present invention comprises identifying part numbers that share a same capacity resource but cannot be made to have a same LLC due to BOM material restriction, where the part numbers which cannot be made to have a same LLC due to the BOM material restriction are oscillating part numbers. Constraints associated with BOM dependency and resource dependency excluding ones associated with oscillating part numbers are identified, and a linear programming formulation is provided which includes the BOM dependency and resource dependency constraints and an objective function defined as sum of the LLC""s for all of the PNs. The linear programming formulation excludes the BOM dependency and resource dependency constraints associated with the oscillating part numbers. The linear programming is then solved by determining a minimum total value of the objective function subject to the BOM dependency and resource dependency constraints to thereby determine modified low level codes.
The present invention is also directed to a system of computing modified low level codes (LLC) for part numbers throughout a bill of material (BOM) supply chain. The system includes a mechanism for identifying part numbers that share a same capacity resource but cannot be made to have a same LLC due to a BOM material restriction and a mechanism for identifying a highest LLC within the part numbers that share the same capacity resource. The system further includes a mechanism for adjusting the LLC for all the part numbers that share the same resource to the highest LLC such that the part numbers, except the OPNs, which share the same capacity resource have a same LLC as well as a mechanism for recalculating the LLC for part numbers which violate BOM dependencies. The system can be implemented via a machine readable code or be hard wired into a circuit or other computational component. The changing of the LLC to the same LLC permits part numbers at different levels of the BOM which share the same capacity resource to be treated at a same level of the BOM in order to sequence the part numbers for resource allocation according to priority ranking based on business rules. The present invention further provides for computer programmable code for implementing the steps of the present invention.